#pragma once
void InsertSort(int* arr, int n)
{
	if (!arr || n < 2)return;
	for (int i = 0; i < n - 1; i++)
	{
		int tmp = arr[i + 1];
		int end = i;
		while(end >= 0)
		{
			if (arr[end] > tmp) 
				arr[end + 1] = arr[end];
			else 
				break;
			end--;
		}
		arr[end + 1] = tmp;
	}
}
//void InsertSort(int* arr, int n)
//{
//	if (!arr || n < 2)return;
//	for (int i = 0; i < n - 1; i++)
//	{
//		int tmp = arr[i + 1];
//		int end = i;
//		while(end >= 0)
//		{
//			if (arr[end] > tmp) 
//				arr[end + 1] = arr[end];
//			else
//			{
//				arr[end + 1] = tmp;
//				break;
//			}
//			end--;
//		}
//	}
//}